package com.cdream.basic.algorithm.leetcode.stack;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author cdream
 * @date 2022/3/24
 */
public class Question503 {
    public static void main(String[] args) {
        new Question503().removeDuplicateLetters("bbcaac");
    }

    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n * 2; i++) {
            int index = i % n;
            if (!stack.isEmpty() && nums[index] > nums[stack.peek()]) {
                int j = stack.poll();
                res[j] = nums[index];
            }
            if (i < n) {
                stack.push(i);
            }
        }
        return res;
    }

    public String removeDuplicateLetters(String s) {
        // 核心思路，去除一个字符让字典序最小的方法是，找到第一个s[i]>=s[i+1]
        int n = s.length();
        LinkedList<Character> stack = new LinkedList<>();
        int[] cnts = new int[26];
        for (char c : s.toCharArray()) {
            cnts[c - 'a']++;
        }
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            while (!stack.isEmpty()&& cnts[stack.peek()-'a']>0 && stack.peek() >= c) {
                stack.poll();
            }
            stack.push(c);
            cnts[c - 'a']--;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pollLast());
        }
        return sb.toString();
    }
}
